Gopher Proxy
gopher.conman.org:70 gopher.conman.org:70/0Phlog:2026/08/06.1
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
* * * * *
Unary operators and the Shunting Yard algorithm
I use the Shunting Yard algorithm [1] to handle precedence when parsing
expressions in my assembler [2]. It's great because not only is it simple to
implement, but it simplifies the code in a hand-written recursive descent
parser [3]. The BNF (Backus-Naur form) is effectively:
-----[ BNF ]-----
; BNF per RFC-5234
expr = factor *(op factor)
op = '*' ; just the basic ops for now
/ '/' ; adding more is just adding
/ '+' ; them to this definition
/ '-'
factor = literal
/ var
/ '(' expr ')'
literal = DIGIT+
var = (ALPHA / '_') (ALPHA / DIGIT / '_')*
-----[ END OF LINE ]-----
When expressing this BNF via a recursive descent parser, the function
handling expr is where the Shunting Yard algorithm is used, providing
precedence handling. In my implementation, the function handling op returns
the precedence and associativity from a table:
-----[ C ]-----
static struct optable const cops[] =
{
[OP_EXP] = { OP_EXP , AS_RIGHT , 1000 } ,
[OP_MUL] = { OP_MUL , AS_LEFT , 900 } ,
[OP_DIV] = { OP_DIV , AS_LEFT , 900 } ,
[OP_MOD] = { OP_MOD , AS_LEFT , 900 } ,
[OP_ADD] = { OP_ADD , AS_LEFT , 800 } ,
[OP_SUB] = { OP_SUB , AS_LEFT , 800 } ,
[OP_SHL] = { OP_SHL , AS_LEFT , 700 } ,
[OP_SHR] = { OP_SHR , AS_LEFT , 700 } ,
[OP_BAND] = { OP_BAND , AS_LEFT , 600 } ,
[OP_BEOR] = { OP_BEOR , AS_LEFT , 500 } ,
[OP_BOR] = { OP_BOR , AS_LEFT , 400 } ,
[OP_WORD] = { OP_WORD , AS_LEFT , 350 } ,
[OP_NE] = { OP_NE , AS_LEFT , 300 } ,
[OP_LT] = { OP_LT , AS_LEFT , 300 } ,
[OP_LE] = { OP_LE , AS_LEFT , 300 } ,
[OP_EQ] = { OP_EQ , AS_LEFT , 300 } ,
[OP_GE] = { OP_GE , AS_LEFT , 300 } ,
[OP_GT] = { OP_GT , AS_LEFT , 300 } ,
[OP_LAND] = { OP_LAND , AS_LEFT , 200 } ,
[OP_LOR] = { OP_LOR , AS_LEFT , 100 } ,
};
-----[ END OF LINE ]-----
Adding a new operator is pretty easy. I was able to add the :: operator
(OP_WORD) and slot it in (the expression a :: b is the same as a * 256 + b
and is used extensively in my 6809 ANS Forth implementation [4]).
The downside, the Shunting Yard algorithm doesn't handle unary operators very
well [5]. From what research I've done and a proof-of-concept I did, it can
be done. Unary operators need to be right associative, but that's the easy
part. It gets ugly with parsing—how to determine if “-” is a subtraction
binary operator or a unary negation operator, and where to place that code,
and it has to go somewhere. I got it working. but it involved smearing the
Shunting Yard algorithm into the op and factor functions in my case. And
honesty, I don't think it's worth it just to get -3**2 to return -9 versus 9.
[1] https://en.wikipedia.org/wiki/Shunting_yard_algorithm
[2] https://github.com/spc476/a09
[3] https://github.com/spc476/a09/blob/400c5033f9952eb33706cefa5ea8f886e211aa8e/expr.c
[4] gopher://gopher.conman.org/0Phlog:2025/06/04.1
[5] gopher://gopher.conman.org/0Phlog:2026/08/01.1
Email Sean Conner at sean@conman.org
.
you're on gopher.conman.org^70/0Phlog:2026/08/06.1
back link is gopher.conman.org:70/1phlog.gopher